package com.sunny.l13;

import java.util.HashMap;
import java.util.Map;

public class Solution {

    /**
     * key: 原节点
     * value: 新节点
     */
    Map<RandomListNode, RandomListNode> map = new HashMap<>();

    public RandomListNode copyRandomList(RandomListNode head) {

        RandomListNode oldp = head;
        if(null == oldp)
            return null;
        RandomListNode newHead = new RandomListNode(head.label);
        RandomListNode newp = newHead;
        map.put(oldp, newp);

        oldp = oldp.next;
        while (null != oldp){
            RandomListNode tmp = new RandomListNode(oldp.label);
            map.put(oldp,tmp);
            newp.next = tmp;
            oldp = oldp.next;
            newp = newp.next;
        }

        oldp = head;
        while (null != oldp){
            map.get(oldp).random = map.get(oldp.random);
            oldp = oldp.next;
        }

        return newHead;
    }
}

class RandomListNode {
    int label;
    RandomListNode next, random;
    RandomListNode(int x) { this.label = x; }
}
